package test;

/**
 * @Description:
 * @author: wangmy169
 * @date: 2023/2/10
 */
import java.util.Scanner;

public class Bag1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt();
            int m = in.nextInt();
            Goods1[] goods = new Goods1[m];
            for(int i = 0; i < m; i++){
                goods[i] = new Goods1();
            }
            for(int i = 0; i < m; i++){
                int v = in.nextInt();
                int p = in.nextInt();
                int q = in.nextInt();
                goods[i].v = v;
                goods[i].p = p*v;
                if(q == 0){
                    goods[i].main = true;
                }else if(goods[q-1].a == -1){
                    goods[q - 1].a = i;
                }else{
                    goods[q - 1].b = i;
                }
            }
            int[][] dp = new int[m + 1][N + 1];
            for(int i = 1; i <= m; i++){
                for(int j = 0; j <= N; j++){
                    dp[i][j] = dp[i - 1][j];
                    if(!goods[i - 1].main){
                        continue;
                    }
                    if(j >= goods[i - 1].v){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - goods[i - 1].v] + goods[i - 1].p);
                    }else if(goods[i - 1].a != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a].v){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - goods[i - 1].v - goods[goods[i - 1].a].v] + goods[i - 1].p + goods[goods[i - 1].a].p);
                    }else if(goods[i - 1].b != -1 && j >= goods[i - 1].v + goods[goods[i - 1].b].v){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - goods[i - 1].v - goods[goods[i - 1].b].v] + goods[i - 1].p + goods[goods[i - 1].b].p);
                    }else if(goods[i - 1].a != -1 && goods[i - 1].b != -1 && j >= goods[i - 1].v + goods[goods[i - 1].a].v + goods[goods[i - 1].b].v){
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - goods[i - 1].v - goods[goods[i - 1].a].v - goods[goods[i - 1].b].v] + goods[i - 1].p + goods[goods[i - 1].a].p + goods[goods[i - 1].b].p);
                    }
                }
            }
            System.out.println(dp[m][N]);
        }
    }
}

class Goods1 {
    int v;
    int p;

    boolean main = false;

    int a = -1;
    int b = -1;
}
